package org.usmile.algorithms.learn.graph.floodfill;

import org.usmile.algorithms.learn.graph.AdjList;
import org.usmile.algorithms.learn.graph.Graph;

public class CCMaxCount {
    public int maxCount(Graph graph) {
        boolean[] visited = new boolean[graph.getV()];
        int maxCount = 0;
        for (int v = 0; v < graph.getV(); v++) {
            if (!visited[v]) {
                maxCount = Math.max(dfs(graph, v, visited), maxCount);
            }
        }

        return maxCount;
    }

    private int dfs(Graph graph, int v, boolean[] visited) {
        visited[v] = true;
        int res = 1;
        for (int w : graph.adj(v)) {
            if (!visited[w]) {
                res += dfs(graph, w, visited);
            }
        }

        return res;
    }

    public static void main(String[] args) {
        Graph graph = new AdjList(5);
        graph.addEdge(0, 1);
        graph.addEdge(1, 2);
        graph.addEdge(1, 4);
        graph.addEdge(2, 4);

        System.out.println(new CCMaxCount().maxCount(graph));
    }
}
